TLDM telah meninggalkan pangkalan bersejarahnya, KD Malaya, di Woodlands, Singapura, untuk pangkalan baru yang lebih moden, yang turut dipanggil KD Malaya, di Lumut, Perak. Pangkalan lain telah dibina dibina di Tanjung Gelang, Kuantan, Pahang, yang turut berkhidmat sebagai Markas Wilayah Laut 1 dan di Tanjung Pengelih, Johor yang berkhidmat sebagai pusat latihan rekrut tentera laut KD Sultan Ismail. Pangkalan turut terdapat di Sungai Antu, Sarawak, di Labuan, dan Sandakan Sabah. Sebuah pangkalan pusat untuk operasi kapal selam telah dibina di Teluk Sepanggar, Sabah yang mana turut berfungsi sebagai Markas Wilayah Laut 2. Sebuah lagi pangkalan sedang dibina di Pulau Langkawi, Kedah untuk dijadikan pusat untuk operasi di Lautan Hindi. Akses ke Lautan Pasifik telah disediakan dengan pangkalan TLDM di Semporna, Sabah. Pemerintahan wilayah TLDM mulanya terbahagi kepada dua kawasan Malaysia Barat (Wilayah Laut I) dan Malaysia Timur atau Sabah dan Sarawak (Wilayah Laut II). Lazimnya pemerintah atau panglima wilayah-wilayah ini berpangkat Laksamana Pertama (satu bintang), tetapi dahulunya pernah juga dijawat pegawai kanan berpangkat Kepten. Pernah juga sesebuah wilayah diketuai oleh seorang Laksamana Muda (dua bintang) baru-baru ini[20]. TLDM juga berhasrat untuk menubuhkan wilayah keempat di Sungai Antu dan menetapkan pemerintahan setiap wilayah untuk seorang Laksamana Muda di masa akan datang.

Senarai pangkalan TLDM

• TLDM Lumut, Perak (Markas Armada)

• TLDM Tanjung Gelang, Pahang (Markas Wilayah Laut I)

• TLDM Teluk Sepanggar, Sabah (Markas Wilayah Laut II)

• TLDM Bukit Malut, Langkawi (Markas Wilayah Laut III)

• TLDM Sejingkat, Sarawak

• TLDM Tanjung Pengelih, (KD Sultan Ismail) Johor

• TLDM Kota Kinabalu

• TLDM Sandakan, Sabah

• TLDM Semporna, Sabah

• Pusat Hidrografi Negara, Pulau Indah, Selangor

Senarai Stesen Komunikasi

• SK TLDM Setiawan, Perak.

• SK TLDM Parit, Perak.

• SK TLDM Kuantan, Pahang.

• SK TLDM Kota Kinabalu

Senarai Unit PSTL (Pasukan Simpanan)

• PSTL Kuching, Sarawak.

• PSTL KD Tawau, Sabah.

• PSTL Sandakan, Sabah.

• PSTL Sri Likas, Sabah.

• PSTL Labuan, Wilayah Persekutuan.

• PSTL Setiu, Terengganu (Dipindahkan dari PSTL Chendering, Terengganu.)

• PSTL Tok Bali, Kelantan.

• PSTL KD Sri Pinang, Pulau Pinang. (Pusat Latihan PSSTLDM)

• PSTL KD Sri Manjung, Perak.

• PSTL KD Sri Klang, Selangor.

• PSTL KD Sri Medini, Johor.